#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/3/31 16:31
# ===========================================
#       题目名称： 39. 组合总和
#       题目地址： https://leetcode.cn/problems/combination-sum/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================

import itertools as _it
import time as _time
import copy as _copy


class Solution:
    """
        思路 ： 可以考虑双指针
    """

    def combinationSum(self, candidates, target):
        """
            双指针 target = 21 案例有问题
        """
        result = []  # 返回值
        candidates.sort()  # 先从小到大排序一下
        possibility_dict = {}  # 可能性字典  key 剩余的结果 value [[], [] ,[]] 可能性
        # 第一次遍历
        for candidate in candidates:
            if candidate == target:
                result.append([candidate])
            elif candidate > target:
                continue
            elif candidate < target:
                res = target - candidate
                possibility = possibility_dict.get(res)
                if possibility:
                    possibility.append([candidate])
                else:
                    possibility_dict[res] = [[candidate]]
        # 遍历所有的可能性
        while possibility_dict:
            temp_possibility_dict = dict()
            for k, v in possibility_dict.items():
                # 1. 通过k 找到剩余的可能性
                if k < candidates[0]:
                    continue
                # 2. 遍历
                for i in range(len(candidates)):
                    candidate = candidates[i]
                    if candidate > k:
                        break
                    if candidate == k:
                        for item in v:
                            item.append(candidate)
                            item.sort()
                            result.append(item)
                    if candidate < k:
                        cur_target = k - candidate
                        # if cur_target < candidates[0]:
                        #     break
                        cur_items = []
                        for item in v:
                            cp_item = _copy.deepcopy(item)
                            cp_item.append(candidate)
                            cur_items.append(cp_item)
                        cur_possibility_list = temp_possibility_dict.get(cur_target)
                        if cur_possibility_list:
                            cur_possibility_list.extend(cur_items)
                        else:
                            temp_possibility_dict[cur_target] = cur_items
            possibility_dict = temp_possibility_dict
        # 去重
        result = set(tuple(item) for item in result)
        result = list(list(item) for item in result)
        return result

    def combinationSum5(self, candidates, target):
        """
            效率不行 最长99秒
        """
        result = []
        # 找出最小数 和 目标值相除 得到最小的排列组合长度
        candidates.sort()
        cur_len = 0

        while cur_len < target:
            cur_len += 1
            # 校验 是否符合最小的 最大的规则
            min_val = 0
            for i in range(cur_len):
                min_val += candidates[0]
            if min_val > target:
                continue
            max_val = 0
            for i in range(cur_len):
                max_val += candidates[len(candidates) - 1]
            if max_val < target:
                continue
            for elements in _it.combinations_with_replacement(candidates, cur_len):
                val = 0
                for element in elements:
                    val += element
                if val == target:
                    result.append(list(elements))

        return result

    def combinationSum4(self, candidates, target):
        """
             穷举
        """
        # 返回值
        result = []
        # 排序
        candidates.sort()
        # 定义字典 k : 剩余值 v [[可能性1]， [可能性2]]
        dict_reminders_list = dict()
        # 初始化一下
        for i in range(len(candidates)):
            if target == candidates[i]:
                result.append([candidates[i], ])
                continue
            dict_reminders_list[target - candidates[i]] = [[candidates[i]], ]
        # 尝试一下各种可能性
        while len(dict_reminders_list) > 0:
            tmp_dict_reminders_list = dict()
            for k, v in dict_reminders_list.items():
                # 1. 判断剩余值是否 k == 目标值
                if k in candidates:
                    for tmp_v in v:
                        cpt_v = _copy.deepcopy(tmp_v)
                        cpt_v.append(k)
                        cpt_v.sort()
                        result.append(cpt_v)
                else:
                    # 此处可以优化
                    for candidate in candidates:
                        if k < candidate:
                            continue
                        else:
                            # 剩余的值
                            reminder = k - candidate
                            # 看看临时字典里面有没有剩余的值
                            reminders_list = tmp_dict_reminders_list.get(reminder)
                            # 如果有
                            if reminders_list:
                                reminders_list = _copy.deepcopy(reminders_list)
                                for reminders in reminders_list:
                                    reminders.append(candidate)
                                tmp_dict_reminders_list[reminder] = reminders_list
                            else:
                                reminders_list = _copy.deepcopy(v)
                                for reminders in reminders_list:
                                    reminders.append(candidate)
                                tmp_dict_reminders_list[reminder] = reminders_list

            dict_reminders_list = tmp_dict_reminders_list
        # 去重
        p1, p2 = 0, 1
        if len(result) > 2:
            while p1 < p2 < len(result):
                if result[p1] == result[p2]:
                    del result[p2]
                else:
                    p1 += 1
                    p2 += 1
        return result

    def combinationSum3(self, candidates, target):
        """
                超出时间限制
            @param candidates:list[int] -> 无重复数组
            @param target:int -> 目标整数
            @result result:list[int] -> 返回值

            import itertools as it
        # https://cloud.tencent.com/developer/article/1650456
        # 使用两个序列进行排列组合
        for e in it.product('AB', 'CD'):
            print(''.join(e), end=', ') # AC, AD, BC, BD,
        print('\n---------')
        # 使用一个序列、重复2次进行全排列
        for e in it.product('AB', repeat=2):
            print(''.join(e), end=', ') # AA, AB, BA, BB,
        print('\n---------')
        # 从序列中取2个元素进行排列
        for e in it.permutations('ABCD', 2):
            print(''.join(e), end=', ') # AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC,
        print('\n---------')
        # 从序列中取2个元素进行组合、元素不允许重复
        for e in it.combinations('ABCD', 2):
            print(''.join(e), end=', ') # AB, AC, AD, BC, BD, CD,
        print('\n---------')
        # 从序列中取2个元素进行组合、元素允许重复
        for e in it.combinations_with_replacement('ABCD', 2):
            print(''.join(e), end=', ') # AA, AB, AC, AD, BB, BC, BD, CC, CD, DD,

        """
        result = []
        # 找出最小数 和 目标值相除 得到最小的排列组合长度
        candidates.sort()
        if target - len(candidates) < 1:
            return result
        for cur_len in range(1, target):
            for elements in _it.combinations_with_replacement(candidates, cur_len):
                val = 0
                for element in elements:
                    val += element
                if val == target:
                    result.append(list(elements))

        return result

    def combinationSum2(self, candidates, target):
        """
            @param candidates:list[int] -> 无重复数组
            @param target:int -> 目标整数
            @result result:list[int] -> 返回值

            import itertools as it
        # https://cloud.tencent.com/developer/article/1650456
        # 使用两个序列进行排列组合
        for e in it.product('AB', 'CD'):
            print(''.join(e), end=', ') # AC, AD, BC, BD,
        print('\n---------')
        # 使用一个序列、重复2次进行全排列
        for e in it.product('AB', repeat=2):
            print(''.join(e), end=', ') # AA, AB, BA, BB,
        print('\n---------')
        # 从序列中取2个元素进行排列
        for e in it.permutations('ABCD', 2):
            print(''.join(e), end=', ') # AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC,
        print('\n---------')
        # 从序列中取2个元素进行组合、元素不允许重复
        for e in it.combinations('ABCD', 2):
            print(''.join(e), end=', ') # AB, AC, AD, BC, BD, CD,
        print('\n---------')
        # 从序列中取2个元素进行组合、元素允许重复
        for e in it.combinations_with_replacement('ABCD', 2):
            print(''.join(e), end=', ') # AA, AB, AC, AD, BB, BC, BD, CC, CD, DD,

        """
        result = []
        # 找出最小数 和 目标值相除 得到最小的排列组合长度
        candidates.sort()
        cur_len, not_find_count = 1, 0
        while cur_len < target and not_find_count < 5:
            is_find = False
            for elements in _it.combinations_with_replacement(candidates, cur_len):
                val = 0
                for element in elements:
                    val += element
                if val == target:
                    is_find = True
                    result.append(list(elements))
            if not is_find:
                not_find_count += 1
            cur_len += 1
        return result


if __name__ == "__main__":
    s = Solution()
    # s1 = _time.time()
    # print(s.combinationSum(candidates=[2, 3, 6, 7], target=7))  # [[2,2,3],[7]]
    # s2 = _time.time()
    # print(s2 - s1)
    # print(s.combinationSum(candidates=[2, 3, 5], target=8))  # [[2,2,2,2],[2,3,3],[3,5]]
    # s3 = _time.time()
    # print(s3 - s2)
    # print(s.combinationSum(candidates=[2], target=1))  # []
    # s4 = _time.time()
    # print(s4 - s3)
    # print(s.combinationSum(candidates=[7, 5, 8, 12, 3, 10, 9, 4, 11, 6], target=21))  # [[12, 9], [10, 11], [7, 7, 7], [7, 5, 9], [7, 8, 6], [7, 3, 11], [7, 10, 4], [5, 5, 11], [5, 8, 8], [5, 12, 4], [5, 10, 6], [8, 3, 10], [8, 9, 4], [12, 3, 6], [3, 9, 9], [9, 6, 6], [4, 11, 6], [7, 7, 3, 4], [7, 5, 5, 4], [7, 5, 3, 6], [7, 8, 3, 3], [7, 4, 4, 6], [5, 5, 5, 6], [5, 5, 8, 3], [5, 8, 4, 4], [5, 3, 3, 10], [5, 3, 9, 4], [5, 4, 6, 6], [8, 3, 4, 6], [12, 3, 3, 3], [3, 3, 9, 6], [3, 3, 4, 11], [3, 10, 4, 4], [3, 6, 6, 6], [9, 4, 4, 4], [7, 5, 3, 3, 3], [7, 3, 3, 4, 4], [5, 5, 5, 3, 3], [5, 5, 3, 4, 4], [5, 3, 3, 4, 6], [5, 4, 4, 4, 4], [8, 3, 3, 3, 4], [3, 3, 3, 3, 9], [3, 3, 3, 6, 6], [3, 4, 4, 4, 6], [5, 3, 3, 3, 3, 4], [3, 3, 3, 3, 3, 6], [3, 3, 3, 4, 4, 4], [3, 3, 3, 3, 3, 3, 3]]
    # s5 = _time.time()
    # print(s5 - s4)
    # print(s.combinationSum(candidates=[6, 36, 34, 20, 12, 18, 27, 28, 7, 37, 19, 30, 8, 2, 35, 39], target=25))  #
    # s6 = _time.time()
    # print(s6 - s5)
    # print(s.combinationSum(candidates=[8, 10, 9, 32, 25, 27, 22, 38, 15, 5, 3, 26, 30, 11, 21, 36, 37], target=39))  #
    # s7 = _time.time()
    # print(s7 - s6)
    print(s.combinationSum(candidates=[3, 5, 7], target=10))
